Range addition

Time: O(K + N); Space: O(1); medium

Assume you have an array of length N initialized with all 0’s and are given K update operations.

Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex … endIndex] (startIndex and endIndex inclusive) with inc.

Return the modified array after all k operations were executed.

Example 1

Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]

Output: [-2,0,3,5,3]

[2]:

class Solution1(object):
    def getModifiedArray(self, length, updates):
        """
        :type length: int
        :type updates: List[List[int]]
        :rtype: List[int]
        """
        result = [0] * length

        for update in updates:
            result[update[0]] += update[2]
            if update[1]+1 < length:
                result[update[1]+1] -= update[2]

        for i in range(1, length):
            result[i] += result[i-1]

        return result

[3]:

s = Solution1()
length = 5
updates = [
    [1, 3,  2],
    [2, 4,  3],
    [0, 2, -2]
]
assert s.getModifiedArray(length, updates) == [-2, 0, 3, 5, 3]

[4]:

class Solution2(object):
    """
    Sweeping line algorithm
    """
    def getModifiedArray(self, length, updates):
        """
        :type length: int
        :type updates: List[List[int]]
        :rtype: List[int]
        """
        res = [0 for _ in range(length)]

        for left, right, inc in updates:
            res[left] += inc
            if right + 1 < length:
                res[right + 1] -= inc

        curr = 0

        for i in range(length):
            curr += res[i]
            res[i] = curr

        return res

[5]:

s = Solution2()
length = 5
updates = [
    [1, 3,  2],
    [2, 4,  3],
    [0, 2, -2]
]
assert s.getModifiedArray(length, updates) == [-2, 0, 3, 5, 3]

[8]:

from heapq import *

class Solution3(object):
    """
    using heapq, But actually no need to use heapq...
    """
    def getModifiedArray(self, length, updates):
        """
        :type length: int
        :type updates: List[List[int]]
        :rtype: List[int]
        """

        q = []

        for left, right, inc in updates:
            q.append([left, inc])
            q.append([right + 1, -inc])

        heapify(q)

        res = [0 for _ in range(length)]

        while q:
            idx, val = heappop(q)
            if idx < length:
                res[idx] += val

        curr = 0
        for i in range(length):
            curr += res[i]
            res[i] = curr

        return res

[9]:

s = Solution3()
length = 5
updates = [
    [1, 3, 2],
    [2, 4, 3],
    [0, 2, -2]
]
assert s.getModifiedArray(length, updates) == [-2,0,3,5,3]